package cn.nawang.ebeim.client.version;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Given numRows, generate the first numRows of Pascal's triangle.

 For example, given numRows = 5, Return

 [
 [1],
 [1,1],
 [1,2,1],
 [1,3,3,1],
 [1,4,6,4,1]
 ]
 * Created by GanJc on 2016/2/24.
 */
public class PascalTriangle {

    public static void main(String[] args) {
        pascalTriangle(0);
        pascalTriangle(3);
        pascalTriangle(4);
        pascalTriangle(6);

        pascalTriangle2(0);
        pascalTriangle2(3);
        pascalTriangle2(4);
        pascalTriangle2(6);

        System.out.println(generate(6));
    }

    public static void pascalTriangle(int n) {
        int tables[][] = new int[n][];
        for (int i = 0; i < n; i++) {
            tables[i] = new int[i + 1];
            tables[i][0] = 1;
            tables[i][i] = 1;
            for (int j = 1; j < i; j++) {
                tables[i][j] = tables[i - 1][j - 1] + tables[i - 1][j];
            }
            System.out.println(Arrays.toString(tables[i]));
        }
        System.out.println("---------------");
    }

    /**
     * Given an index k, return the kth row of the Pascal's triangle.
     * For example, given k = 3, Return [1,3,3,1].
     */
    public static List<Integer> pascalTriangle2(int n) {
        List<Integer>list = new ArrayList<>();
        int row[] = new int[n+1];
        row[0] = 1;
        for (int i = 1; i < n+1; i++) {
            for (int j = i; j > 0; j--) {
                row[j] = row[j] + row[j - 1];
            }
        }
        for (int i : row) {
            list.add(i);
        }
        return list ;
    }

    public static List<List<Integer>> generate(int n) {
        List<List<Integer>> lists = new ArrayList<>();
        List<Integer> pre = null ;
        for (int i = 0; i < n; i++) {
            List<Integer>list = new ArrayList<>();
            list.add(0,1);
            if(pre!=null){
                for (int j = 1; j < i; j++) {
                    list.add(j,pre.get(j-1)+pre.get(j));
                }
            }
            if(i>0){
                list.add(i,1);
            }
            lists.add(list);
            pre = list ;
        }
        return lists;
    }


}
